DISMUTAZIONI
CON RIPETIZIONE DOPPIE

Spigazione di come mi riconduco alla notazione con $|H \cap \sigma H|$ e come modificarla.

A000459.
Vogliamo contare le dismutazioni di {1,1,2,2,3,3,...n,n}:
Ossia cerco $\sigma \in S_n$ che applicata alla stringa 1...2n rispetti entrambe le condizioni:
Notazione: stringhe senza parentesi, permutazioni scritte in cicli tra parentesi tonde.

Spiegazione dell'ultima freccia: $\sigma \circ 1,2...n = \sigma \tau ^{-1} (\tau \circ$1,2...n) nessun punto in comune con $\tau \circ$1...n $\rightarrow \sigma \tau ^{-1} \in H_n$ per definizione $\rightarrow \sigma \in H_n \tau$.
Nota: Adesso abbiamo un metodo generale per passare da "non ha punti in comune con XXXX" a $\in H \tau$.

Nota: Il coniugio è una bigezione e preserva la scrittura in cicli, H è definito da questa (tutte e sole le permutazioni di lunghezza massima), quindi H è invariante per coniugio.
$\sigma H \sigma^{-1} = H \rightarrow \ H \sigma = (\sigma H \sigma^{-1}) \sigma = \sigma H$.

Così possiamo concludere che il numero di dismutazioni di {1,1,2,2,3,3...n,n} è: $$ \frac{|H_{2n} \cap (1,n+1)(2,n+2)(3,n+3)...(n,2n)H_{2n}|}{2^n}$$

Aldilà della riformulazione, per risolvere il problema mi riconduco alla tecnica "dell'hotel" (Vedi prima spiegazione per rettangoli latini) e con il principio di inclusione-esclusione ottengo: $$ \frac{1}{2^n}* \sum_{i+2j+k=2n} (-1)^{2n-i}* \binom{n}{j} * \binom{n-j}{k}*2^k *i^{2j}*(i-1)^{2k}*(i-2)^{(i-k)}$$ Per più dettagli: j.boncompagni@studenti.unipi.it


Codice python per verificare:

import math
def dism2(n):
  if n==0: return 1
  s=0
  for h in range (0,2*n+1):
   for j in range (0, h+1):
    if h-2*j>=0 and n>=h-j:
     k=h-2*j
     i=2*n-h
     a=math.comb(n,j)*math.comb(n-j,k)*pow(2,k)*pow(i,2*j)*pow(i-1,2*k)*pow(i-2,i-k)*pow(-1,k%2)
     s+=a
  return s/pow(2,n)

for n in range (0,11):
  print(dism2(n))

#coincide con OEIS :)


Nota: anche altre scritture in bicicli erano equivalenti, si tratta solo di rinominare (o di identificare diversamente all'inizio), inoltre posso spezzare in più bicicli:
$|H_{2n} \cap (1,n+1)(2,n+2)(3,n+3)...(n,2n)H_{2n}| = |H_{2n} \cap (1,2)(3,4)(5,6)...(2n-1,2n)H_{2n}| = |H_{2n} \cap (1,2)H_{2n} \cap (3,4)H_{2n} \cap ...(2n-1,2n)H_{2n}|$.
L'unica cosa che conta è che i vincoli siano gli stessi, ad esempio: niente punti in comune con "12345, 31254 e 23145" è uguale a niente punti in comune con "12345, 21345, 32145, 13245 e 12345", si vede chiaramente impilando le righe che ogni colonna ha tutti e soli gli stessi vincoli. Passando alla notazione con le dismutazioni:
$|H \cap (123)(45)H \cap (132)H| = |H \cap (12)H \cap (13)H \cap (23)H \cap (45)H|.$
Abbiamo un metodo per riscrivere alcune intersezioni tra H e i suoi traslati.
Ad esempio due permutazioni disgiunte ($\sigma$, $\tau$) sono sempre "unibili", come nel caso sopra dei bicicli:
$|H \cap \sigma \tau H|$ = $|H \cap \sigma H \cap \tau H|.$

Nota: questo approccio è generalizzabile a dismutazioni con ripetizioni generiche: {1,1...1,2,2...2,3...3...n...n}.
Chiamiamo $k_i$ il numero di volte che compaiono numeri <=i, allora i sarà presente $k_i-k_{i-1}$ volte.
Adesso possiamo procedere come prima rinominando tutto in ordine e identificando 1,2...$k_1$ tra loro, poi $k_1$+1...$k_2$ etc.
Cerchiamo permutazioni {1,2...$k_n$} con il vincolo che 1,2...$k_1$ non siano nei primi $k_1$ posti, $k_1$+1...$k_2$ non siano nei $k_1$+1...$k_2$ posti e così via. A meno di identificazione.
Il primo vincolo è rappresenzatibili da "nessun punto in comune con" un insieme di stringhe che hanno ogni elemento 1-$k_1$ in ogni posizione tra 1-$k_1$ (e fissano il resto) ($\star$) , ad esempio (1,2...$k_1$) e le sue potenze - applicate a 1...$k_n$.
In base a questa scelta otteniamo identità come prima, ad esempio potevo prendere tutti i bicicli contenenti 1-$k_1$.
Analogamente imponiamo i vincoli per il resto della stringa e possiamo passare alla notazione con le dismutazioni: $$ \frac{1}{k_1!*(k_2-k_1)!*...*(k_n-k_{n-1})!} |\bigcap_{i=1}^{k_1} (1,2...k_1)^iH \ \cap \ \bigcap_{i=1}^{k_2-k_1} (k_1+1...k_2)^iH \ \cap... \bigcap_{i=1}^{k_n-k_{n-1}} (k_{n-1}+1...k_n)^iH|.$$ Ad esempio dism. di {1111223} le vedo come permutazioni di 1...7 senza punti in comune con "1234567, 4123567, 3412567, 2341567 e 1234657" cioè:
$$\frac{1}{4!*2!}*|\bigcap_{i=0}^3 (1,2,3,4)^iH \ \cap \ (5,6)H|.$$ Ora uniamo i vincoli (come prima) e chiamiamo m:= max {$k_i-k_{i-1}$}, possiamo concludere che il numero cercato è: $$\frac{1}{k_1!*(k_2-k_1)!*...*(k_n-k_{n-1})!}*|\bigcap_{i=1}^{m} (1,2...k_1)^i \circ (k_1+1...k_2)^i \circ ... (k_{n-1}+1...k_n)^iH|$$ Continuando l'esempio: sto unendo i vincoli in "412365, 341256, 234165 e 123456", cioè:
$$\frac{1}{4!*2!}*|\bigcap_{i=1}^4 (1,2,3,4)^i(5,6)^iH|.$$


$\star$: può essere interessante chiedersi quali sottoinsiemi di $S_k$ godano di questa proprietà, cioè che applicati a 1...k mandino ogni elemento in ogni posizione.
Ad esempio un k-ciclo e le sue potenze oppure tutti i bicicli.
Perchè sono tutti i modi di riscrivere qualcosa che mi rappresenta dismutazioni con ripetizione (da approfondire).


Jack Boncompagni.